package com.wj.algorithm.lintcode.string;

public class P79 {
    
    public int longestPrefix(String a, String b) {
        int c = 0;
        for(int i = 0, al = a.length(), bl = b.length(); i < al && i < bl; i ++) {
            if(a.charAt(i) == b.charAt(i)) {
                c ++;
            } else {
                return c;
            }
        }
        return c;
    }
    
    public int longestCommonSubstring(String A, String B) {
        if(A == null || B == null) {
            return 0;
        }
        
        int al = A.length();
        int bl = B.length();
        
        int aindex = -1, bindex = 0;
        
        int max = 0;
        
        while(aindex < al && bindex < bl) {
            for(int i = bindex; i < bl; i ++) {
                char target = B.charAt(i);
                while(true) {
                    aindex = A.indexOf(target, aindex + 1);
                    if(aindex < 0) {
                        aindex = 0;
                        break;
                    }
                    
                    String Asub = A.substring(aindex);
                    String Bsub = B.substring(i);

                    int tempMax = longestPrefix(Asub, Bsub);
                    if(tempMax > max) {
                        max = tempMax;
                    }
                }
            }
            
            bindex ++;
            aindex = 0;
        }
        
        return max;
    }
    
    
    public static void main(String[] args) {
        
        System.out.println(new P79().longestCommonSubstring("abccccccccccde", "dbccccccabccde"));
    }
}
